home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / str.exe / MATCH.CPP < prev    next >
C/C++ Source or Header  |  1993-03-15  |  15KB  |  515 lines
  1. /*
  2.  *
  3.  * Author:    Allen I. Holub 
  4.  *
  5.  * (c) C Gazette. May be used freely as long as author and publication are
  6.  * acknowledged 
  7.  *
  8.  * Roy S. Woll                (Revision 2.0)
  9.  * 1032 Summerplace Dr.
  10.  * San Jose, CA 95122
  11.  *
  12.  * ---------------------------------------------------------------------- 
  13.  *
  14.  *
  15.  * Revision 2.02  14 Mar 1993 ROY S. WOLL
  16.  *
  17.  *   Fixed octal set definition to include first octel digit
  18.  *
  19.  * Revision 2.0   16 Nov 1992 ROY S. WOLL
  20.  *
  21.  *   Initial revision for match.c -> match.cpp
  22.  *   Compatibility with C++ syntax, and now member functions of regX.h
  23.  *   to avoid polluting the name space.  
  24.  *   Fixed some inconsistencies. Regular expression compiled pattern should 
  25.  *   now grow as needed.  Case insensitive support.
  26.  *   
  27.  * Revision 1     27 Jan 1991 Allen I. Holub
  28.  *
  29.  */
  30.  
  31. #include <stdio.h>
  32. #include <ctype.h>
  33. #include <string.h>
  34.  
  35. #include "regximp.h"
  36.  
  37. inline const char * max(const char * x, const char * y)
  38.    {if (x>y) return x; else return y;}
  39.  
  40. /* Metacharacters in the input:         */
  41. #define BOL     '^'     /* start-of-line anchor                 */
  42. #define EOL     '$'     /* end-of-line anchor                   */
  43. #define ANY     '.'     /* matches any character                */
  44. #define CCL     '['     /* start a character class              */
  45. #define CCLEND  ']'     /* end a character class                */
  46. #define NCCL    '^'     /* negates character class if 1st char. */
  47. #define CLOSURE '*'     /* Kleene closure (matches 0 or more)   */
  48. #define PCLOSE  '+'     /* Positive closure (1 or more)         */
  49. #define OPT     '?'     /* Optional closure (0 or 1)            */
  50.  
  51. typedef enum action {      // These are put in the pattern string
  52.                            // to represent metacharacters.
  53.   M_BOL =    (0x80 | '^'), 
  54.   M_EOL =    (0x80 | '$'),
  55.   M_ANY =    (0x80 | '.'),
  56.   M_CCL =    (0x80 | '['),
  57.   M_OPT =    (0x80 | '?'),
  58.   M_CLOSE =  (0x80 | '*'),
  59.   M_PCLOSE = (0x80 | '+')
  60. } action;
  61.  
  62.  
  63.  
  64. typedef unsigned char pattern;   /* pattern strings are unsigned char */
  65.  
  66. #define IS_ACTION(x) ((x)&0x80)  /* true => element of pat. string is an   */
  67.                                 /* action that represents a metacharacter */
  68.  
  69. /*----------------------------------------------------------------------*/
  70. #define MAPSIZE 16  /* need this many bytes for character class bit map */
  71.  
  72. /*
  73.  * Advance a pointer into the pattern template 
  74.  * to the next pattern element, this is a +1 for
  75.  * all pattern elements but M_CCL, where you
  76.  * to skip past both the M_CCL character and the
  77.  * bitmap that follows that character
  78.  */
  79.  
  80. #define ADVANCE(pat) (pat += (*pat == (pattern)M_CCL) ? (MAPSIZE+1) : 1)
  81.  
  82. //
  83. // Bitmap functions. Set bit b in the map and
  84. // test bit b to see if it was set previously.
  85. //
  86. #define SETBIT(b,map) ((map)[((b) & 0x7f) >>3] |= (1<< ((b) & 0x07)) )
  87. #define TSTBIT(b,map) ((map)[((b) & 0x7f) >>3] &  (1<< ((b) & 0x07)) )
  88.  
  89. int regXimp::omatch(const char ** strp, const pattern * pat, 
  90.                      const char * start)
  91. {
  92.   /*
  93.    * Match one pattern element, pointed at by pat, against the character at
  94.    * **strp. Return 0 on a failure, 1 on success. *strp is advanced to skip
  95.    * over the matched character on a successful match. Closure is handled one
  96.    * level up by patcmp(). 
  97.    *
  98.    * "start" points at the character at the left edge of the line. This might
  99.    * not be the same thing as *strp if the search is starting in the middle
  100.    * of the string. An end-of- line anchor matches '\n' or '\0'. 
  101.    */
  102.  
  103.   int advance = -1;        // amount to advance *strp, -1 == error
  104.  
  105.   switch (*pat) {
  106.   case M_BOL:              // First char in string?
  107.     if (*strp == start)    // Only one star here.
  108.       advance = 0;
  109.     break;
  110.  
  111.   case M_ANY:              // . = anything but newline
  112.     if (**strp != '\n') advance = 1;
  113.     break;
  114.  
  115.   case M_EOL:
  116.     if (**strp == '\n' || **strp == '\0')
  117.       advance = 0;
  118.     break;
  119.  
  120.   case M_CCL:
  121.     if (TSTBIT(**strp, pat + 1)) advance = 1;
  122.     break;
  123.  
  124.   default:        /* literal match */
  125.     if (caseSensitive){
  126.       if (**strp == *pat) advance = 1;
  127.     }
  128.     else if (toupper(**strp) == toupper(*pat)) advance = 1;
  129.     break;
  130.   }
  131.  
  132.   if (advance > 0)
  133.     *strp += advance;
  134.  
  135.   return (advance + 1);
  136. }
  137.  
  138. #define ISOCTDIGIT(x) ('0'<=(x) && (x)<='7')
  139.  
  140. static int hex2bin(int c)
  141. {
  142.      /* Convert the hex digit represented by 'c' to an int. 'c'
  143.       * must be one of: 0123456789abcdefABCDEF
  144.       */
  145.      return (isdigit(c) ? (c)-'0': ((toupper(c))-'A')+10)  & 0xf;
  146. }
  147.  
  148. static int oct2bin(int c)
  149. {
  150.      /* Convert the hex digit represented by 'c' to an int. 'c'
  151.       * must be a digit in the range '0'-'7'.
  152.       */
  153.      return ( ((c)-'0')  &  0x7 );
  154. }
  155.  
  156.  
  157.  
  158. /*------------------------------------------------------------*/
  159.  
  160. int     esc(const char **s)
  161. {
  162.      /* Map escape sequences into their equivalent symbols. Return
  163.       * the equivalent ASCII character. *s is advanced past the
  164.       * escape sequence. If no escape sequence is present, the
  165.       * current character is returned and the string is advanced by
  166.       * one. The following are recognized:
  167.       *
  168.       *  \b     backspace
  169.       *  \f     formfeed
  170.       *  \n     newline
  171.       *  \r     carriage return
  172.       *  \s     space
  173.       *  \t     tab
  174.       *  \e     ASCII ESC character ('\033')
  175.       *  \DDD   number formed of 1-3 octal digits
  176.       *  \xDDD  number formed of 1-3 hex digits
  177.       *  \^C    C = any letter. Control code
  178.       */
  179.  
  180.      int rval;
  181.  
  182.      if( **s != '\\' )
  183.           rval = *( (*s)++ );
  184.      else {
  185.           ++(*s);                               // Skip the '\'
  186.           switch( toupper(**s) ) {
  187.             case '\0':  rval = '\\';             break;
  188.             case 'B':   rval = '\b' ;            break;
  189.             case 'F':   rval = '\f' ;            break;
  190.             case 'N':   rval = '\n' ;            break;
  191.             case 'R':   rval = '\r' ;            break;
  192.             case 'S':   rval = ' '  ;            break;
  193.             case 'T':   rval = '\t' ;            break;
  194.             case 'E':   rval = '\033';           break;
  195.  
  196.             case '^':   
  197.               rval = *++(*s) ;
  198.               rval = toupper(rval) - '@' ;
  199.               break;
  200.  
  201.             case 'X':   
  202.               rval = 0;
  203.               ++(*s);
  204.               if( isxdigit(**s) ) {
  205.                    rval  = hex2bin( *(*s)++ );
  206.               }
  207.               if( isxdigit(**s) ) {
  208.                    rval <<= 4;
  209.                    rval  |= hex2bin( *(*s)++ );
  210.               }
  211.               if( isxdigit(**s) ) {
  212.                    rval <<= 4;
  213.                    rval  |= hex2bin( *(*s)++ );
  214.               }
  215.               --(*s);
  216.               break;
  217.  
  218.             default:
  219.               if( !ISOCTDIGIT(**s) )
  220.                    rval = **s;
  221.               else {
  222.                    rval = oct2bin( *(*s)++ );
  223.                    if( ISOCTDIGIT(**s) ) {
  224.                         rval <<= 3;
  225.                         rval  |= oct2bin( *(*s)++ );
  226.                    }
  227.                    if( ISOCTDIGIT(**s) ) {
  228.                         rval <<= 3;
  229.                         rval  |= oct2bin( *(*s)++ );
  230.                    }
  231.                    --(*s);
  232.               }
  233.               break;
  234.           }
  235.           ++(*s);
  236.      }
  237.      return rval;
  238. }
  239.  
  240.  
  241. /*----------------------------------------------------------------------*/
  242. const char * regXimp::doccl(const char * src)
  243. {
  244.   /*
  245.    * Set bits in the map corresponding to characters specified in the src
  246.    * character class.  
  247.    */
  248.  
  249.  
  250.   int                first, last, negative;
  251.  
  252.   ++src;                        // skip past the [
  253.   negative = (*src == NCCL);
  254.   if (negative) ++src;          // check for negative ccl
  255.  
  256.   const char * start = src;     // start of characters in class
  257.  
  258.   int len = compiledPattern.length();
  259.   compiledPattern.pad(len+MAPSIZE, str::right, char(0));
  260.   char * map = (char *)compiledPattern(len);
  261.  
  262.   while (*src && *src != CCLEND) {
  263.     if (*src != '-') {
  264.